package com.atcumt.Carl.String;

import java.util.Stack;

public class String01 {

    /*
     * 字符串相加
     * carry:计算进位
     * tmp:计算当前位的和
     */
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry != 0) {
            int x = i < 0 ? 0 : num1.charAt(i--) - '0';
            int y = j < 0 ? 0 : num2.charAt(j--) - '0';
            int tmp = x + y + carry;
            carry = tmp / 10;

            sb.append(tmp % 10); // 添加到字符串尾部
        }
        return sb.reverse().toString();
    }

    /*
     * 字符串相乘
     * num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
     * 例: 123 * 45,  123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中
     */
    public String multiply(String num1, String num2) {
        int n1 = num1.length()-1;
        int n2 = num2.length()-1;
        if(n1 < 0 || n2 < 0) {
            return "";
        }
        int[] mul = new int[n1 + n2 + 2];
        
        for(int i = n1; i >= 0; --i) {
            for(int j = n2; j >= 0; --j) {
                int bitmul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');      
                bitmul += mul[i+j+1]; // 先加低位判断是否有新的进位
                
                mul[i+j] += bitmul / 10;
                mul[i+j+1] = bitmul % 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // 去掉前导0
        while(i < mul.length-1 && mul[i] == 0){
            i++;
        } 
        for(; i < mul.length; ++i){
            sb.append(mul[i]);
        }  
        return sb.toString();
    }


    /**
     * 字符串转换为数字
     */
    public int myAtoi (String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int index = 0;

        // 1、去掉前导空格
        while (index < n && chars[index] == ' ') {
            index++; // 判断下标越界得写前面
        }
        if (index == n) {
            return 0; // 去除空格后到末尾
        }

        // 2、判断正负, flag 标识负数
        boolean flag = false;
        if (chars[index] == '-') {
            flag = true;
            index++;
        } else if (chars[index] == '+') {
            index++;
        } else if (!Character.isDigit(chars[index])) {
            return 0;
        }

        // 3、识别数字，字符串转整数
        int res = 0;
        while (index < n && Character.isDigit(chars[index])) {
            int digit = chars[index] - '0';
            if (res > (Integer.MAX_VALUE - digit) / 10) {
                return flag ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            res = res * 10 + digit;
            index++;
        }
        return flag ? -res : res;
    }


    /**
     * 玩筹码
     * 判断pos里奇数多还是偶数多，如果奇数多，返回偶数的个数，如果偶数多，返回奇数的个数
     */
    public int minCostToMoveChips(int[] pos) {
        int odd = 0, even = 0;
        for (int i = 0; i < pos.length; i++) {
            if (pos[i] % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return Math.min(even, odd);
    }

    /**
     * 字符串解码
     * 输入：s = "3[a2[c]]"
     * 输出："accaccacc"
     */
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        String str = "";
        int num = 0; // 初始化
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0'; // 倍数
            } else if (c == '[') {
                // 入栈
                numStack.push(num);
                num = 0;
                strStack.push(str);
                str = "";
            } else if (c == ']'){
                // 出栈
                String strTemp = "";
                int repeat = numStack.pop();
                for (int j = 0; j < repeat; j++) {
                    strTemp += str;
                }
                str = strStack.isEmpty() ? strTemp : strTemp + strStack.pop();
            } else {
                // 遇到字母直接追加
                str += c;
            }
        }
        return str;
    }
}
